插头dp——从入门到跳楼

前置知识

  • 动态规划
  • 括号表示法(或最小表示法)
  • 状态压缩
  • 哈希表

一些定义

先看模板题:P5056@洛谷 - 【模板】插头dp

插头 dp 主要用于解决网格图上的哈密顿回路相关的问题。

插头

插头就是网格图上一个格子与另一个格子相连的位置,如图。

轮廓线

在我们指定一个当前格子时,他的下侧和右侧连接到边界的线成为轮廓线。

如图,蓝色格子为当前格子,红色线为轮廓线。

毒瘤动规 - 插头 dp

设计状态

插头 dp 中状态为一条轮廓线,每次状态转移转移一个格子,轮廓线转移如图:

状态压缩

由于数据量太大,这里需要使用状态压缩。

我们知道,为了形成回路,在任意时刻插头均不会相交。(红色为插头,绿色为轮廓线)

于是想到括号串。这里我们用 (())#\# 来表示轮廓线为在左侧的插头、在右侧的插头或没有插头。

因为需要状态压缩,我们考虑使用括号表示法(最小表示法也可以,但在本文中不会涉及)。在这里我们将 0,1,20,1,2 分别表示空插头、左侧插头和右侧插头。

状态转移

状态转移有如下几种情况:

当前格为障碍

若当前格为障碍,直接转移即可。

当前格既没有上插头又没有左插头

此时为了满足经过所有格子,添加右侧和下侧的插头,即在括号串中将一对 0000 替换为 1212

当前格有上插头

则有两种转移方式——直走延长插头或转弯。

当前格有左插头

同理。

当前格既有上插头又有左插头

均为 11 或均为 22

此时将两个 1122)合并变为 00,并向右侧(左侧)找到第一个右插头(左插头)变为左插头(右插头)。

左插头为 22、上插头为 11

此时直接连起来即可。

左插头为 11、上插头为 22

此时将要形成闭合回路。判断当前格是否为最后一格,是则连接并更新答案,否则状态不合法。

其他细节

我们建立滚动哈希表方便压缩空间,同时 dp 只记录哈希位置的值。因为是哈希表,因此在每一行开始的时候都需要 modifyQue() 来滚动、更换值。

完整代码

您大可先看看我 23 次才 AC 的提交记录

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define fil(a,b) memset((a),(b),sizeof(a))
#define in inline
using namespace std;
typedef long long ll;
const ll N = 12+5, X = 3e5+5, K = 1<<25|5, mod = 299987;
ll n, m, dx, dy, bit, lst, ans;
ll a[N][N], p[N], h[X], nxt[K], que[2][K], val[2][K], cnt[2];
in void add(ll hash, ll status, ll tot) {
	nxt[++cnt[bit]] = h[hash];
	h[hash] = cnt[bit];
	que[bit][cnt[bit]] = status;
	val[bit][cnt[bit]] = tot;
}
in void insert(ll status, ll tot) {
	int hash = status % mod + 1;
	for(ll i=h[hash];i;i=nxt[i]) {
		if(que[bit][i] == status) {
			val[bit][i] += tot;
			return;
		}
	}
	add(hash, status, tot);
}
in void modifyQue() {
	for(ll i=1;i<=cnt[bit];i++) {
		que[bit][i] <<= 2;
	}
}
in void dp() {
	cnt[bit] = 1;
	val[bit][1] = 1;
	que[bit][1] = 0;
	for(ll i=1;i<=n;i++) {
		modifyQue();
		for(ll j=1;j<=m;j++) {
			fil(h, 0);
			lst = bit;
			bit ^= 1;
			cnt[bit] = 0;
			for(ll k=1;k<=cnt[lst];k++) {
				ll status = que[lst][k];
				ll tot = val[lst][k];
				ll P1 = (status >> ((j - 1) * 2)) % 4;
				ll P2 = (status >> (j * 2)) % 4;
				if(!a[i][j]) {
					if(!P1 && !P2) {
						insert(status, tot);
					}
				}
				else if(!P1 && !P2) {
					if(a[i][j+1] && a[i+1][j]) {
						ll nxtStatus = status + p[j-1] + 2 * p[j];
						insert(nxtStatus, tot);
					}
				}
				else if(!P1 && P2) {
					if(a[i][j+1]) {
						insert(status, tot);
					}
					if(a[i+1][j]) {
						ll nxtStatus = status - p[j] * P2 + p[j-1] * P2;
						insert(nxtStatus, tot);
					}
				}
				else if(P1 && !P2) {
					if(a[i+1][j]) {
						insert(status, tot);
					}
					if(a[i][j+1]) {
						ll nxtStatus = status - p[j-1] * P1 + p[j] * P1;
						insert(nxtStatus, tot);
					}
				}
				else if(P1 == 1 && P2 == 1) {
					ll tmp = 1;
					for(ll l=j+1;l<=m;l++) {
						ll Pid = (status >> (l * 2)) % 4;
						if(Pid == 1) {
							++tmp;
						}
						else if(Pid == 2) {
							--tmp;
						}
						if(!tmp) {
							ll nxtStatus = status - p[j] - p[j-1] - p[l];
							insert(nxtStatus, tot);
							break;
						}
					}
				}
				else if(P1 == 2 && P2 == 2) {
					ll tmp = 1;
					for(ll l=j-2;l>=0;l--) {
						ll Pid = (status >> (l << 1)) % 4;
						if(Pid == 1) {
							--tmp;
						}
						else if(Pid == 2) {
							++tmp;
						}
						if(!tmp) {
							ll nxtStatus = status - 2 * p[j] - 2 * p[j-1] + p[l];
							insert(nxtStatus, tot);
							break;
						}
					}
				}
				else if(P1 == 2 && P2 == 1) {
					ll nxtStatus = status - 2 * p[j-1] - p[j];
					insert(nxtStatus, tot);
				}
				else if(i == dx && j == dy) {
					ans += tot;
				}
			}
		}
	}
}

int main() {
	scanf("%lld%lld", &n, &m);
	for(ll i=1;i<=n;i++) {
		string s;
		cin>>s;
		s = ' ' + s;
		for(ll j=1;j<=m;j++) {
			if(s[j] == '.') {
				a[i][j] = 1;
				dx = i;
				dy = j;
			}
		}
	}
	p[0] = 1;
	for(ll i=1;i<=12;i++) {
		p[i] = p[i-1] << 2;
	}
	dp();
	printf("%lld\n", ans);
	return 0;
}